#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/random/linear_congruential.hpp>
using namespace boost;

#include <iostream>
using namespace std;

#include <ctime>

void test( unsigned int N, unsigned int M, unsigned int seed)
{
  typedef adjacency_list<setS,vecS,directedS> graph_t;

  clock_t start, finish;

  graph_t g;
  
  // generate random graph
  boost::minstd_rand gen( seed);
  start =clock();
  generate_random_graph( g, N, M, gen
			 , false // allow_parallel
			 , false // self_edges
			 );
  finish =clock();
  std::cout <<(double)(finish - start)/(double)CLOCKS_PER_SEC 
	    <<" ";
  
  // breadth_first_search
  default_bfs_visitor vis;
  start =clock();    
  breadth_first_search( g, 0, visitor( vis));    
  finish =clock();
  
  std::cout <<(double)(finish - start)/(double)CLOCKS_PER_SEC 
	    <<std::endl;    
}

int main( int argc, char* argv[])
{
  unsigned int N;
  unsigned int M;
  unsigned int seed =1;

  if ( argc ==3){
    N =atoi( argv[1]);
    M =atoi( argv[2]);
  }
  else if( argc ==4){
    N =atoi( argv[1]);
    M =atoi( argv[2]);
    seed =atoi( argv[3]); 
  }
  else {
    std::cerr <<"usage: bfs nodes edges seed" <<std::endl;
    exit( 1);
  }

  test( N, M, seed);

  return 0;
}
